//
// Created by user on 2022/3/15.
//
#include <iostream>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
    };

ListNode* middleNode(ListNode* head) {
    if (head== nullptr) return nullptr;
    //1.计算链表的长度
    int length = 0;
    ListNode *curr = head;
    while (curr!= nullptr){
        length++;
        curr = curr->next;
    }
    //2.找到链表的中间节点
    for (int i = 0; i < length/2; ++i) {
        head = head->next;
    }

    return head;
}

ListNode* middleNode1(ListNode* head) {
    //快慢指针
    if (head== nullptr) return nullptr;
    ListNode *slow = head;
    ListNode *fast = head;
    while (fast!= nullptr && fast->next!= nullptr){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}